package com.wu.reconstructbinarytree;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        return buildBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }
    /**
     *           1
     *        /    \
     *      2        3
     *    /       /  \
     *  4       5     6
     *   \            /
     *    7         8
     */
    /**
     * 前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
     */
    /**
     * 1.根据前序序列第一个结点确定根结点
     * 2.根据根结点在中序序列中的位置分割出左右两个子序列
     * 3.对左子树和右子树分别递归使用同样的方法继续分解
     */
    public TreeNode buildBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        int rootVal = pre[preL];
        TreeNode rootTree = new TreeNode(rootVal);

        /**索引，划分左右子树*/
        int index = 0;
        for (int i = inL; i <= inR; i++) {
            if (in[i] == rootVal) {
                index = i;
                break;
            }
        }
        //左边子树长度
        int leftLen = index - inL;
        //右边子树长度
        int rightLen = inR - index;
        rootTree.left = buildBinaryTree(pre, preL + 1, preL + leftLen, in, inL, index - 1);
        rootTree.right = buildBinaryTree(pre, preR - rightLen + 1, preR, in, index + 1, inR);
        return rootTree;
    }
}